#include <stdlib.h>
#include <string.h>
#include <stdio.h>

struct entry {
	struct entry * next;
	int found;
	char word[];
};

static struct entry * entries[1000000] = {};

static unsigned int hash_string(const char * string)
{
	unsigned int hashval;
	
	hashval = 0;
	for (; *string != '\0'; string++) {
		hashval = (hashval << 5) - hashval;
		hashval += *string;
	}
	hashval %= sizeof(entries) / sizeof(*entries);
	
	return hashval;
}

static void insert_entry(const char * word,
			 size_t size)
{
	unsigned int index;
	struct entry * entry;

	index = hash_string(word);
	entry = malloc(sizeof(*entry) + size);
	memcpy(entry->word, word, size);
	entry->found = 0;
	entry->next = entries[index];
	entries[index] = entry;
}

static int search_entry(const char * word)
{
	unsigned int index;
	struct entry * entry;
	
	index = hash_string(word);
	for (entry = entries[index]; entry != NULL; entry = entry->next) {
		if (strcmp(entry->word, word) == 0) {
			int found;
			
			found = entry->found;
			entry->found = 1;
			
			return found ^ 1;
		}
	}
	
	return 0;
}

static void read_dictionary(FILE * dictionary)
{
	char * buff;
	size_t size;
	
	buff = NULL;
	size = 0;
	for (;;) {
		ssize_t read;
		
		read = getline(&buff, &size, dictionary);
		if (read <= 0)
			return;
		buff[read - 1] = '\0';
		insert_entry(buff, read);
	}
	free(buff);
}

static void exchange_beginning(char * string,
			       size_t i)
{
	char temp1, temp2;
	
	temp1 = string[i];
	temp2 = string[0];
	
	string[i] = temp2;
	string[0] = temp1;
}

static void print_anagrams(size_t len,
			   char * mix,
			   char * all)
{
	size_t i;
	
	if (len == 0) {
		if (search_entry(all))
			printf("%s\n", all);
		return;
	}
	
	for (i = 0 ; i < len; i++) {
		exchange_beginning(mix, i);
		print_anagrams(len - 1,
			       mix + 1,
			       all);
		exchange_beginning(mix, i);
	}
}

int main(int argc, char ** argv)
{
	FILE * dictionary;
	
	dictionary = fopen("/usr/share/dict/words", "r");
	if (dictionary == NULL) {
		printf("unable to open dictionary\n");
		return 1;
	}
	read_dictionary(dictionary);
	fclose(dictionary);
	
	if (argc != 2) {
		printf("need single input word\n");
		return 1;
	}
	search_entry(argv[1]);
	print_anagrams(strlen(argv[1]),
		       argv[1], argv[1]);
	
	return 0;
}
